"""
矩阵连乘的动态规划
以最优化方式进行矩阵乘法
假设A[1:n]为n个可连乘的矩阵设其维数：矩阵Ai为p(i-1) × p(i)
则这n个矩阵的参数为 p(0),p(1),p(2),...,p(n)
两矩阵A[i],A[i+1]相乘的计算量为p(i-1)*p(i)*p(i+1)
A[i:j]为A[i]到A[j]的连乘
m[i:j]为A[i]到A[j]连乘的最小计算量
            0   ; i=j
m[i:j] =
            min{m[i:k] + m[k+1:j] + p(k-1)p(k)p(j)} ;  i<=k<j,i<j<=n,k有j-i个可能
s[i:j]为在地k个矩阵断开，的k值
"""

import numpy as np


def MatrixChain(p, n, m, s):
    # # 初始化m[i:j]对角线为0
    # for pos in range(1, n + 1):
    #     m[pos][pos] = 0

    for row in range(2, n + 1):
        for i in range(1, n - row + 1 + 1):  # 开始是1到n-1行，实际是i从1到n-row+1
            j = i + row - 1  # 一开始j从1+2-1=2列到n列       实际是j 从i+1到i+n-1
            # 即 j <= n-row+1+row-1 = n
            m[i][j] = m[i + 1][j] + p[i - 1] * p[i] * p[j]
            s[i][j] = i
        for k in range(i + 1, j):
            t = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]
            if t < m[i][j]:
                m[i][j] = t
                s[i][j] = k
    print("计算量矩阵m:\n", m, "\n断开位置矩阵s:\n", s)


def TraceBack(s, i, j):
    if i == j:
        return
    TraceBack(s, i, s[i][j])
    TraceBack(s, s[i][j] + 1, j)
    print("乘：A", i, ", ", s[i][j], "and A", s[i][j] + 1, ", ", j)


p = [30, 35, 15, 5, 10, 20, 25]
m = np.zeros(((len(p)), (len(p))), dtype=int)
s = np.zeros(((len(p)), (len(p))), dtype=int)
MatrixChain(p, len(p) - 1, m, s)
TraceBack(s, 1, len(p) - 1)
